//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 8 
// -10 <= nums[i] <= 10 
// 
// Related Topics 数组 回溯 
// 👍 878 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermutationsIi {
    public static void main(String[] args){
        int[] nums = {1,1,1,2};
        new PermutationsIi().new Solution().permuteUnique(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        List<List<Integer>> res;
        List<Integer> temp;
        int len;
        boolean[] visited;
        int[] nums;
        public List<List<Integer>> permuteUnique(int[] nums) {
            res = new ArrayList<>();
            temp = new ArrayList<>();
            Arrays.sort(nums);//先对数组进行排序，先排序才能进行剪枝
            this.len = nums.length;
            visited = new boolean[len];
            this.nums = nums;
            dfs();
            return res;
        }

        private void dfs() {
            if (temp.size() == len){
                res.add(new ArrayList<>(temp));
            }else {
                for (int i = 0; i < len; i++) {
                    //对数组进行排序之后，这里是防止重复访问的条件
                    //如果i处值==i-1处值，而且i-1处没被访问，那么如果对当前i进行递归结果会与i-1相同
                    //所以就要跳过当前i，因为i-1如果为false说明是刚刚撤销使用
                    //因为正常遍历时i-1一定会比i先访问到，所以i-1如果未访问只能是已经递归结束了赋值的false
                    //如果i-1在使用中，那么当前i也是可以使用的
                    if (i!=0&&nums[i]==nums[i-1]&&!visited[i-1])continue;//TODO 这个地方是真的巧妙的剪枝
                    if (visited[i]) continue;
                    visited[i] = true;
                    temp.add(nums[i]);
                    dfs();
                    temp.remove(temp.size()-1);
                    visited[i] = false;
                }
            }
        }



        //二刷，使用一个used数组完成同层去重并避免同一支重复使用
        public void dfs(int[] nums, boolean[] used, List<Integer> temp){
            if (temp.size() == nums.length) res.add(new ArrayList(temp));
            else{
                for (int i = 0; i < nums.length; i++){
                    //这里包括了同层去重，以及避免同一支重复引用
                    if ((i > 0 && nums[i] == nums[i-1] && !used[i-1]) || used[i]) continue;
                    used[i] = true;
                    temp.add(nums[i]);
                    dfs(nums, used, temp);
                    temp.remove(temp.size()-1);
                    used[i] = false;
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}